Polar GP
怎么这么困难
被大佬带飞
Two Spanning Trees
并非简单题
你先搞出来一棵 A 的生成树,如果它不是 B 的生成树,那么直接返回它即可。
然后我就不会做了……
首先你发现取 n−1 条边而不构成树,那么必然会构成环。
那么你发现我们只要取到一个边集 C,使得 C 在 B 中构成环,且在 A 中不构成环(即构成森林)即可。
得到他之后,只要在 A 的各连通块中任意连边即可得到一个合法解,所以这是充要的。
考虑上面找到的生成树,记为 T。
为了方便,我们决定考虑所有的环图,即度数等于 0 或 2 的图,显然是等价的。
根据环基方面的理论,我们知道 B 的所有环子图,由所有 T 的非树边生成。
考虑所有 T 的非树边 e,即 e∈/T,定义 {e}∪s1(e) 表示 e 在 A 的 T 上生成的环,s2 类似。
如果我们找到一个 s1(e)⊈s2(e),那么 {e}∪s2(e) 直接就是一组解。
所以现在所有 s1(e)⊆s2(e)。
考虑答案的环基是 E,是所有非树边的一个子集。
那么我们要求 E∪⨁e∈Es2(e) 在 A 中形如一片森林。
记 Cyc2(E)=⨁e∈Es2(e),Cyc1 类似。
则我们要求 ∀E′⊆E,Cyc1(E′)⊈Cyc2(E)。
引入神秘记号:记 e∼e′,如果 s1(e)∩s1(e′)=∅。记 e≈e′,如果存在 e∼e1∼e2∼⋯∼ek∼e′。
显然可达性 ≈ 为一等价关系,可以把 E 划分为 E1⊔E2⊔⋯⊔Ek。
注意到
Cyc2(E)=Cyc1(E1)⊕e∈E1⨁(s2(e)⊕s1(e))⊕Cyc2(E\E1)=Cyc1(E1)⊕e∈E1⨁(s2(e)\s1(e))⊕Cyc2(E\E1)
由于 Cyc1(E1)⊈Cyc2(E),所以要么存在 e∈E1,s2(e)\s1(e)∩Cyc1(E1)=∅,要么存在 e∈E\E1,s2(e)∩Cyc1(E1)=∅。
无论如何,都必然存在 e∈E,(s2(e)\s1(e))∩Cyc1(E1)=∅。
记 e1→e2,如果 (s2(e1)\s1(e1))∩s1(e2)=∅
于是根据 ∼ 和 → 可以建出一个混合图 G。
根据上面的结论,任意一个 ∼ 的连通块都必然存在一条入边。
可以证明 G 中任意一个至少包含一个 → 的简单环都是合法的。
所以可以建图跑 Tarjan,只要存在强连通分量内部包含至少一条 → 即合法。
Christmas Tree
注意到每个点的贡献是它能够到达的点的个数。
设 fu,i 表示 u 能够到达子树外的点的个数为 i 时,u 的子树内的最小代价和。
但是我场上发现,当我想要每次加入一个儿子时,我还要知道 u 在子树内能够到达多少个点,这样肯定会超时。
其实你发现,如果 u 的父边向其父亲,那么我们只想知道它能够到达子数外多少个点;否则我们只想知道它能够到达子树内多少个点。
所以我们再设 gu,i 表示 u 能够到达子树内的点的个数为 i 时,u 的子树内的最小代价和。
转移时不妨预定 u 总共能到达点的个数 k,于是转移形如树上背包。
注意到我们总是从小的 k 转移到大的 k,因此外层枚举了一个 k 之后不难做到 O(n2) 树上背包,所以总复杂度为 O(n3)。
Roman Numerals
赛时猜了一个错误的结论:以为每个点的相对系数不变,所以乘上 LCA 的系数即可。
发现假掉之后,吸取教训想了想 CDQ 分治,但是没想出来。
实际上你发现,找到 LCA 即最大值之后,变成左边剩一个后缀,右边剩一个前缀。
你发现:如果我们算出整个数组的一个后缀的答案,再减去 LCA 及以后的部分的话,刚好就是整个后缀的贡献;前缀同理。
而我们刚好有 O(N) 或者 O(NlogN) 增量构造笛卡尔树的方法。
一个类似扫描线单调栈的东西维护右链
Disjoint Set Splitting
场上首先想出一个错误做法:先随便搞出一棵生成树,维护每条树边有没有删去,以及维护已被删去的树边上的覆盖的非树边的数目。
然后我奋斗 1h+ 写了一个树剖线段树,贡献一发罚时之后,发现做法假掉了……
想想也是,要是动态树那么简单,大家还写什么 LCT 和 ETT 呢?
然后我思考半晌,发现这个强制在线是假的!
具体来说,由于答案一定是一段前缀 1 加上一段后缀 0,而且我们不用管后缀 0 阶段的输入,所以我们其实是可以算出来解密后的输入是什么的。
然后我光速写了一个二分+DFS 的交了上去,然后发现被卡了……
不是你 O(nlogn),n≤106 跑进 2.5s 不是稀疏平常的事情吗卡我干什么啊
冷静一下,发现二分是没有必要的。
我们像那个模板题那样倒序做用 DSU 维护即可。
然后最后 30min 没写出来这个……gg
成功贡献一车罚时
Maximum Segment Sum
场上看一个人都没过就没看,其实不算难
考虑从左到右扫一遍,维护当前后缀和的最大值 cur,则我们要么做 cur←cur+1,要么 cur←max(cur−1,0),然后这个过程中 cur 的最大值即为最大子段和。
然后你发现这个形如格路计数,熟悉反射容斥的小朋友们大概很容易就做出来了。
This Time I Will Be Lucky
也没有看……
等等我是不是在哪里见过?
哦哦应该不是
形如
f(a,b)=max(0,a+ba(f(a−1,b)+1)+a+bb(f(a,b−1)−1))
注意到答案没让我们取模,而且精度仅要求 10−6。
注意到如果每次不是减一而是减 ε→0+ 的话,我们实际上只会取到 y=abx 的 (x,y)。
所以这启示我们只要取接近 y=abx 的直线的附近的点进行计算即可。
Far Away
qtr 花了很久没想出来。
当时就隐隐约约觉得是不是在哪里见过了,场后降智解除之后忽然就发现确实做过的。
其实这道题是概率正确的。
如果在点数 ≤2×104 的连通块内,就直接输出 NO。
否则随机撒 300 个左右的点,跑 BFS,对每个询问 check 一次最短路,那么答案不正确当且仅当 (x,y) 的最短路完美避开了这 300 个点,概率是很低的。
Absolutely Flat
没看
考虑求出每个给定区间的已知元素中的 min 和 max,能否要求区间内的未知元素都在这个区间之内?
不难发现出现冲突当且仅当两个区间有交,且交集全部未确定。
还是很难做。考虑如果只有 0 和 1 能不能做。
那么我们就是要最小化同时有 0 和 1 的区间的数目。
承续上面的结构,我们发现难做的点形如 000???111???000???111...,其中每个区间只包括 0 和 ? 或者 1 和 ?。
每段颜色合并一下,其实难用 DP 解决。
Two Permutations
根本瞪不出来。
记 pi,j 表示 p1∼i 中 ≤j 的元素的数量。
那么结论是:合法当且仅当 pi,j≥qi,j,∀i,j。
虽然赛时想过逆序对方面的东西,但是没想到是这样刻画的。
证明太神秘了,赛时通过的人注意力惊人
首先必要性是显然的,因为操作只会让顺序对数量减少。
对于充分性,我们给出一个构造算法。
取最小的 x 使 p−1(x)=q−1(x),显然此时必然 p−1(x)<q−1(x)。
令 k 为满足 p−1(x)<k≤q−1(x) 且 pk>x 的最小下标,这样的 k 必然存在。
我们断言:对于所有 p−1(x)≤l<k 且所有 x≤y<pk 必然有 pl,y>ql,y。
因此可以把 x 与 pk 交换。
重复此操作即可使 p=q。
One Permutation
可以猜想答案是凹的。
所以可以 WQS 二分。常规的 WQS 二分只能求出来一个值,怎么办呢?注意到只有 n 个 k 是有用的。这是因为答案的规模是 O(n) 的,显然斜率段数不可能很多。
注意这并不意味 k=O(n),因为可能很陡。
每次怎么求出一个有用的 k?考虑维护一个 k 的区间,如果 L 和 R 得到的解是相同的,那么不用继续递归下去了。否则二分一下。
于是形如线段树修改,不增加时间复杂度的规模。
每次用一个树状数组维护 DP 即可。然后就做完了。时间复杂度 O(nnlogn)
Game on Board
qtr 场切了 %%%
注意到由于 x 和 y 不消失,所以实际上 max,max−gcd,max−2×gcd,…,max−k×gcd 都会出现。
所以判断一下游戏进行多少轮即可。